package com.ry.day1129;


//归并排序
public class GuibingSort {

    public static int[] guibing(int[] arr){

        int n = arr.length;
        int step=1;
        while (step<n){
            int L=0; //左组开始的地方
            while (L<n){
                int m = L+step-1; //左组结束的位置
                if(m>n-1) break;
                int r = Math.min(m+step,n-1); //右组结束的位置
                combine(arr,L,m,r);
                L=r+1;
            }
            if(step>n/2) break;
            step=step*2;
        }
        return arr;
    }

    public static void combine(int[] arr,int l ,int m,int r){
        int i=0;
        int p1=l;
        int p2=m+1;
        int[] help = new int[r-l+1];
        while (p1<=m && p2<=r){
            if(arr[p1]<=arr[p2]){
                help[i++] = arr[p1++];
            }else{
                help[i++] = arr[p2++];
            }
        }

        while (p1<=m) {
            help[i++] = arr[p1++];
        }

        while (p2<=r){
            help[i++]= arr[p2++];
        }

        for (int j = 0; j <i ; j++) {
            arr[j+l]= help[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = {9,8,15,14,-1,3,4,22,19,17};
        int[] arr1 = guibing(arr);
        for (int i : arr1) {
            System.out.print(i+" ");
        }
    }
}
